package com.LeeCode;

/**
 * 累加数
 */

public class Code306 {
    public static void main(String[] args) {
        String num = "011";
        System.out.println(new Code306().isAdditiveNumber(num));
    }

    public boolean isAdditiveNumber(String num) {
        if (num == null || num.length() < 3) return false;

        int n = num.length();
        for (int i = 1; i <= n / 2; i++) { // 第一个数的长度
            if (i > 1 && num.charAt(0) == '0') continue; // 前导0
            long first = Long.parseLong(num.substring(0, i));

            for (int j = 1; Math.max(i, j) <= n - i - j; j++) { // 第二个数的长度
                if (j > 1 && num.charAt(i) == '0') continue; // 前导0
                if (i + j == n) continue;

                long second = Long.parseLong(num.substring(i, i + j));
                if (backtrack(num, i + j, first, second)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backtrack(String num, int start, long first, long second) {
        if (start == num.length()) {
            return true;
        }

        long sum = first + second;

        // 构造 sum 的字符串形式，检查是否出现在 num 的 start 位置
        String sumStr = String.valueOf(sum);
        if (num.startsWith(sumStr, start)) {
            // 前导0判断
            if (sumStr.length() > 1 && num.charAt(start) == '0') {
                return false;
            }
            return backtrack(num, start + sumStr.length(), second, sum);
        }

        return false;
    }
}
